package cn.rocky.prepare;

import java.util.TreeMap;

public class maximumRobots {

    public int maximumRobots(int[] chargeTimes, int[] runningCosts, long budget) {
        int n = chargeTimes.length, ans = 0;
        // 记录窗口左右边界
        int left = 0, right = 0;
        // 记录窗口中各个值的状态
        long cost = 0, maxv = 0, sum = 0;
        while (left < n && right <= n){
            // 当当前开销小于budget时，右移right指针
            if (cost < budget){
                ++right;
                if (right > n) break;
                // 更新开销和窗口大小
                maxv = Math.max(maxv, chargeTimes[right - 1]);
                sum += runningCosts[right - 1];
                cost = maxv + (right - left) * sum;
                if (cost <= budget) ans = Math.max(ans, right - left);
            }else{
                // 当当前开销大于等于budget时，右移left指针
                ++left;
                if (left >= n) break;
                // 重新计算开销
                sum -= runningCosts[left - 1];
                maxv = 0;
                for (int i = left; i < right; ++i){
                    maxv = Math.max(maxv, chargeTimes[i]);
                }
                cost = maxv + (right - left) * sum;
            }
        }
        return ans;
    }


    public int maximumRobots1(int[] chargeTimes, int[] runningCosts, long budget) {
        TreeMap<Integer, Integer> treeMap = new TreeMap<>((a, b) -> (b - a));
        int l = 0, r = 0, n = chargeTimes.length;
        long sum, pre = 0;
        int ans = 0;
        while (r < n) {
            pre += runningCosts[r];
            treeMap.put(chargeTimes[r], treeMap.getOrDefault(chargeTimes[r], 0) + 1);
            sum = treeMap.firstKey() + (r - l + 1) * pre;
            while (sum > budget) {
                pre -= runningCosts[l];
                int val = treeMap.get(chargeTimes[l]);
                if (--val == 0) treeMap.remove(chargeTimes[l]);
                else treeMap.put(chargeTimes[l], val);
                l++;
                if (!treeMap.isEmpty())
                    sum = treeMap.firstKey() + (r - l + 1) * pre;
                else sum = 0;
            }
            ans = Math.max(ans, r - l + 1);
            r++;
        }
        return ans;
    }
}
